package Linked;

import java.util.Iterator;

public class List implements Iterable<Integer>{
    private  Node sentry;

    static class Node {
        public int value;
        public Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    public List() {
        sentry = new Node(-1,null);
    }

    //头插节点
    public void addFirst(int value) {
        sentry.next = new Node(value,sentry.next);
    }

    //尾插节点
    public void addLast( int value) {
        Node temp = sentry;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = new Node(value,null);
    }

    //重写迭代器
    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = sentry.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }

    //去重方法二(保留):双指针
    public List removeDoublePointer(List list) {
        if (list == null) {
            return null;
        }

        //少于两个节点，不存在重复的值
        if (list.sentry.next == null || list.sentry.next.next == null) {
            return null;
        }

        Node n1 = list.sentry.next;
        Node n2;

        while ((n2 = n1.next) != null) {

            if (n2.value == n1.value) {
                n1.next = n2.next;
            }else {
                n1 = n1.next;
            }
        }

        return list;
    }


    //去重方法一(保留):递归
    public List removeRecursion(List list) {
        Node sentry1 = list.sentry;
        sentry = recursion1(sentry1);
        return list;
    }

    private Node recursion1(Node p) {

        if (p == null || p.next == null) {
            return p;
        }
        if (p.value == p.next.value) {
            return recursion1(p.next);
        }else {
            p.next = recursion1(p.next);
            return p;
        }

    }



    //去重方法一(不保留):递归
    public List removeRepeat(List list) {
        Node temp = list.sentry;
        sentry = recursion(temp);
        return list;
    }

    public Node recursion(Node p) {
        if (p == null || p.next == null) {
            return p;
        }

        if (p.value != p.next.value) {
            p.next = recursion(p.next);
            return p;
        }else {
            while (p.value == p.next.value) {
                p = p.next;
            }
            return recursion(p.next);
        }

    }


    //去重方法二(不保留):三指针
    public List removeThreePointer(List list) {

        if (list == null) {
            return null;
        }

        Node n1 = list.sentry;
        Node n2 ;
        Node n3 ;
        while ((n2 = n1.next) != null && (n3 = n2.next) != null) {
            if (n2.value == n3.value) {
                while (n3 != null && n2.value == n3.value) {
                    n3 = n3.next;
                }
                n1.next = n3;
            }else {
                n1 = n1.next;
            }
        }
        return list;
    }


    //合并升序链表
    public static List combinedList(List l1,List l2) {
        if (l1 == null && l2 == null) {
            return null;
        } else if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }

        List newList = new List();
        Node node1 = l1.sentry.next;
        Node node2 = l2.sentry.next;
        Node p = newList.sentry;

        while (node1 != null && node2 != null) {

            if (node1.value < node2.value) {
                p.next = node1;
                node1 = node1.next;
            }else {
                p.next = node2;
                node2 = node2.next;
            }
            p = p.next;
        }

        if (node1 != null) {
            p.next = node1;
        }
        if (node2 != null) {
            p.next = node2;
        }
        return newList;
    }

    //合并链表:递归实现
    public List combineList(List list2) {
        List newList = new List();
        Node p1 = this.sentry.next;
        Node p2 = list2.sentry.next;
        Node p = combineRecursion(p1,p2);
        newList.sentry.next = p;
        return newList;
    }

     private Node combineRecursion(Node p1, Node p2) {
        if (p1 == null) {
            return p2;
        } else if (p2 == null ) {
            return p1;
        }

        if (p1.value < p2.value) {
            p1.next = combineRecursion(p1.next,p2);
            return p1;
        }else {
            p2.next = combineRecursion(p1,p2.next);
            return p2;
        }

     }

     //实现多个升序链表合并
    public List moreCombine(Node[] nodes) {
        List list = new List();
        list.sentry.next = moreCombineRecursion(nodes,0, nodes.length-1);
        return list;
    }

    private Node moreCombineRecursion(Node[] nodes,int i,int j) {

        if (j == i) {
            return nodes[i];
        }
        int mid = (i + j) >>> 1;
        Node left = moreCombineRecursion(nodes,i,mid);
        Node right = moreCombineRecursion(nodes,mid+1,j);
        return combineRecursion(left,right);
    }

}
